#include<stdio.h>

#include "bfs.h"

llist bfs(Matrix *matrix, int depart)
{
  int nombre_action = 2;
  //printf("j'entre dans bfs\n");
  int* liste_bfs = malloc(sizeof(int)* (matrix->size));
  int a = 0;
  //printf("je remplis la liste de -1\n");
  for(a ; a <= matrix->size ; a++) { 
    liste_bfs[a] = -1; 
    //printf("liste_bfs[%d] = %d",a, liste_bfs[a]);  
    nombre_action++;
  }
  liste_bfs[0] = depart;
  //printf("bfs[0] = %d et bfs[1] = %d\n", liste_bfs[0], liste_bfs[1]);
  int i = 0; // position du curseur dans la liste_bfs
  int j = 0; // position du curseur dans la colonne de la valeur de la liste_bfs
  int position = 1; // position d'insertion d'un nouvel élément
  int sommet_actuel ; // valeur du sommet actuel (rang)
  //for (i ; i < (matrix->size) ; i++) // on parcourt tout le tableau liste_bfs
  //printf("Je suis devant le while bfs[i] = %d - i = %d et matrix->size = %d\n", liste_bfs[i], i, matrix->size );
  nombre_action+= 4;
  while((liste_bfs[i] != -1) && (i < matrix->size))
  {
    //printf("%s\n", str);
    //printf("Je suis DANS le while sommet_actuel (bfs[i]) = %d - i = %d\n", liste_bfs[i], i );
    sommet_actuel = liste_bfs[i]; // on récupère la valeur du tableau a la position i
    j=0;
    for(j ; j < (matrix->size) ; j++) { // on parcourt ensuite chaque ligne de la matrice dont la valeur de la colonne est sommet_actuel
      //printf("Je rentre dans la premiere boucle pour tester ci dessous s'il y a une arrete entre sommet actuel : %d et j : %d\n",sommet_actuel, j );
      if(matrix->table[sommet_actuel][j] > 0) { // s'il y a un 1 donc une arete
	//printf("Je suis dans le if, il y a donc une arete, je regarde maintenant si le sommet j (%d) est deja dans la liste\n",j);
	int k = 0; // compteur pour un parcours de liste_bfs pour voir si le sommet qu'on evalue est deja dans la liste ou pas
	int present = 0; // test pour voir si le sommet evalué est deja dans la liste ou pas
	for( k ; k <= (matrix->size) ; k++) // on regarde si le sommet est deja present
	{
	    //printf("if j == liste_bfs[k]\n",j, liste_bfs[k]);
	    if(j == liste_bfs[k]) // si c'est le cas
	    {
	      //printf("OUI, donc on incremente present\n");
	      present++; // on incremente present
	    }
	    nombre_action++;
	}
	//printf("On regarde si present == 0 : %d == 0\n",present);
	if(present == 0) { // si ce sommet n'etait pas présent
	  //printf("OUI ! donc on peut ajouter le sommet j (%d) dans la liste BFS à la position : %d\n",j, position);
	  liste_bfs[position] = j; // on le rajoute a la liste
	  //printf("On a bien : liste_bfs[position] = %d = %d\n",liste_bfs[position], j);
	  position++; // on met a jour la prochaine position libre
	}
      }
      nombre_action++;
    }
    i++;
  }
  /*int y = 0;
  for(y ; y <= matrix->size; y++)
  {
      printf("liste_bfs[%d] : %d\n",y,liste_bfs[y]);
  }*/
  // On a donc un tableau contenant la BFS (puis des -1 si pas totalement remplie)
  int z = 0; // dernier parcours, promis !
  llist resultat = NULL;
  while(liste_bfs[z] != -1 && z < matrix->size)
  {
    //printf("j'entre dans le while pour remplir la liste : %d\n",liste_bfs[z]);
    resultat = ajouterEnFin(resultat, liste_bfs[z]);
    /*printf("AFFICHAGE DE LA LISTE ---------------\n");
    afficherListe(resultat);*/
    z++;
    nombre_action++;
  }
  /*printf("AFFICHAGE DE LA LISTE ---------------\n");
  afficherListe(resultat);
  printf("AFFICHAGE DE LA LISTE ---------------\n");*/
  
  printf("-- Pour information la fonction BFS a effectue %d actions (a ajouter aux nombres d'actions faites par les fonctions appelees dans celle-ci) --\n\n", nombre_action+1);
  
  
  return resultat;
}
